The present invention relates to data compression systems and methods, and more specifically, to data compression with random access.
Compression of large databases not only reduces disk storage, it can also speed up query answering by reducing the bulk that has to be pushed through the increasingly narrow (relative to CPU speed) disk I/O bottleneck. Various techniques for compressing data are commonly used in the communications and computer fields.
The prior art in database compression falls roughly into two major categories; Record Level Compression and Block Level or File Level Compression. Record Level Compression is less accurate and has a low compression ratio, but generally is much faster in compression processing. Also, Record Level Compression techniques yield a greater degree of data compression. Block Level Compression, for example, variants of LZ77 & LZW algorithms are very accurate and have higher compression ratios, but are much slower in compression processing. Unfortunately, the prior methods of data compression are less favorable for database-like applications, which generally require random access to data. So, a need exists for a more effective and efficient compression technique which is suitable for this class of applications, which is presented in this invention in the manner described below.